// 实现二叉搜索树

class TreeNode {
	data: any;
	left: TreeNode | null = null;
	right: TreeNode | null = null;

	constructor(data: any) {
		this.data = data;
	}
}

class BinarySearchTree {
	root: null | TreeNode = null;
	// 先序遍历
	preOrderTraverse(): Array<any> {
		if (this.root === null) {
			return [];
		}
		const stack: Array<TreeNode> = [this.root];
		const result: Array<any> = [];
		while (stack.length) {
			const current: TreeNode = stack.pop()!;
			result.push(current.data);
			if (current.right !== null) {
				stack.push(current.right);
			}
			if (current.left !== null) {
				stack.push(current.left);
			}
		}
		return result;
	}

	// 中序遍历
	inOrderTraverse(): Array<any> {
		if (this.root === null) {
			return [];
		}
		const stack: Array<TreeNode> = [];
		const result: Array<any> = [];
		let current: TreeNode | null = this.root;
		while (stack.length || current !== null) {
			while (current !== null) {
				stack.push(current);
				current = current.left;
			}
			if (stack.length) {
				current = stack.pop()!;
				result.push(current.data);

				current = current.right;
			}
		}
		return result;
	}

	// 后序遍历
	postOrderTraverse(): Array<any> {
		if (this.root === null) {
			return [];
		}

		const stack: Array<TreeNode> = [];
		const result: Array<any> = [];
		let current: TreeNode | null = this.root;
		let lastNode: TreeNode | null = null;

		while (stack.length || current !== null) {
			while (current !== null) {
				stack.push(current);
				current = current.left;
			}

			current = stack[stack.length - 1];

			if (current.right !== null && current.right !== lastNode) {
				current = current.right;
			} else {
				lastNode = stack.pop()!;
				result.push(lastNode.data);
				current = null;
			}
		}

		return result;
	}

	// 插入元素
	insert(node: TreeNode): boolean {
		if (this.root === null) {
			this.root = node;

			return true;
		}

		let parent: null | TreeNode = null;
		let current: TreeNode | null = this.root;

		while (current !== null) {
			parent = current;
			if (node.data <= current.data) {
				current = current.left;
			} else {
				current = current.right;
			}
		}

		if (node.data <= parent!.data) {
			parent!.left = node;
		} else {
			parent!.right = node;
		}
		return true;
	}

	// 查找指定元素
	search(data: any): boolean {
		let current = this.root;
		while (current !== null) {
			if (current.data === data) {
				return true;
			}
			if (data <= current.data) {
				current = current.left;
			} else {
				current = current.right;
			}
		}
		return false;
	}

	// 获取最小最大值
	getMin(): any {
		let current = this.root;
		if (current === null) {
			return null;
		}

		while (current.left !== null) {
			current = current.left;
		}

		return current.data;
	}

	getMax(): any {
		let current = this.root;
		if (current === null) {
			return null;
		}

		while (current.right !== null) {
			current = current.right;
		}

		return current.data;
	}

	// 删除元素
	remove(target: any): boolean {
		let current = this.root;
		let parent: null | TreeNode = null;
		let isLeftNode = true;
		// 如果root为空，就返回false
		if (current === null) {
			return false;
		}

		while (current !== null && current.data !== target) {
			parent = current;
			if (target < current.data) {
				current = current.left;
				isLeftNode = true;
			} else if (target > current.data) {
				current = current.right;
				isLeftNode = false;
			}
		}

		// 没有找到
		if (current === null) {
			return false;
		}

		// 找到了
		// 第一种情况：判断如果没有孩子
		if (current.left === null && current.right === null) {
			// 如果删除的节点是root
			if (parent === null) {
				this.root = null;
			}
			// 如果当前节点是父节点的左节点
			else if (isLeftNode) {
				parent.left = null;
			}
			// 如果当前节点是右节点
			else if (!isLeftNode) {
				parent.right = null;
			}
			return true;
		}

		// 第二种情况，有孩子
		const successor = this.getSuccessor(current);
		successor.left = current.left;
		successor.right = current.right;
		// 如果删除的节点是root
		if (parent === null) {
			this.root = successor;
		}
		// 如果当前节点是父节点的左节点
		else if (isLeftNode) {
			parent.left = successor;
		}
		// 如果当前节点是右节点
		else if (!isLeftNode) {
			parent.right = successor;
		}
		return true;
	}

	// 获取指定节点的最近的前驱或者后驱节点
	getSuccessor(target: TreeNode): TreeNode {
		let parent: null | TreeNode = null;
		let current = target;
		let isLeftNode = true;
		// 优先寻找后继节点
		if (current.right !== null) {
			parent = current;
			current = current.right;
			isLeftNode = false;
			while (current.left !== null) {
				parent = current;
				current = current.left;
				isLeftNode = true;
			}
			// 移除目标节点的父母节点对其的引用
			if (isLeftNode) {
				parent.left = current.right;
			} else {
				parent.right = current.right;
			}
		} else if (current.left !== null) {
			parent = current;
			current = current.left;
			isLeftNode = true;
			while (current.right !== null) {
				parent = current;
				current = current.right;
				isLeftNode = false;
			}
			// 移除目标节点的父母节点对其的引用
			if (isLeftNode) {
				parent.left = current.left;
			} else {
				parent.right = current.left;
			}
		}
		return current;
	}
}
